Joe Doliner

Exercise from: http://programmingpraxis.com/2009/10/16/growable-arrays/

Our goal here is to implement an array which is capable of dynamically growing as we add elements to it at the cost of logarithmic runtime for put and get functions instead of the constant runtime of standard arrays.

The indexing scheme seems a bit weird at first until we notice the pattern that the left subtree of 1 is all even and the right subtree is all odd. So given and index we simply consider its parity and choose the correct subtree. Then we apply this recursively to the subtree with the index halved (rounded down). Here it is implemented in python:

class exArray():
	key = None
	left = None
	right = None
	def get(self, index):
		if (index == 0):
			print 'index out of bounds'
		elif (index == 1):
			if (self.key == None):
				print 'index out of bounds'
			else:
				return self.key
		elif (index%2 == 0):
			if (self.left):
				return self.left.get(index >> 1)
			else:
				print 'index out of bounds'
		else:
			if (self.right):
				return self.right.get(index >> 1)
			else:
				print 'index out of bounds'
	def put(self, index, key):
		if (index == 0):
			print 'index out of bounds'
		elif (index == 1):
			self.key = key
		elif (index%2 == 0):
			if (not self.left):
				self.left = exArray()
			self.left.put(index >> 1, key)
		else:
			if (not self.right):
				self.right = exArray()
			self.right.put(index >> 1, key)

Full code: exArray.py
To use:

import exArray
exArray.test(array_size)

Tags: programming

This entry was posted on Friday, October 16th, 2009 at 8:07 pm and is filed under Programming Praxis. You can follow any comments to this entry through the RSS 2.0 feed. Responses are currently closed, but you can trackback from your own site.